/**
 * @file categories/graph/traveling_salesman/poj3311
 * @brief 旅行商问题
 * @see
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @copyright 2022
 * @date 2022/7/18 19:29:39
 **/

#include <iostream>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int dis[12][12];
int dp[1 << 11][12];
int main() {
  // High rating and good luck!
  int n;
  while (cin >> n && n) {
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= n; ++j) cin >> dis[i][j];

    for (int k = 0; k <= n; ++k)
      for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
          if (dis[i][k] + dis[k][j] < dis[i][j])
            dis[i][j] = dis[i][k] + dis[k][j];

    for (int s = 0; s <= (1 << n) - 1; ++s) {
      for (int i = 1; i <= n; ++i) {
        if (s & (1 << (i - 1))) {
          if (s == (1 << (i - 1)))
            dp[s][i] = dis[0][i];
          else {
            dp[s][i] = INF;
            for (int j = 1; j <= n; ++j) {
              if (s & (1 << (j - 1)) && j != i)
                dp[s][i] = min(dp[s ^ (1 << (i - 1))][j] + dis[j][i], dp[s][i]);
            }
          }
        }
      }
    }
    int minn = dp[(1 << n) - 1][1] + dis[1][0];
    for (int i = 2; i <= n; ++i)
      if (dp[(1 << n) - 1][i] + dis[i][0] < minn)
        minn = dp[(1 << n) - 1][i] + dis[i][0];
    cout << minn << endl;
  }
  return 0;
}
